package jianzhioffer.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 二维数组的查找
 * 给一个二维数组，从左到右，从上到下，有序。
 * 给一个数字，确认数字是否在该数组中
 *
 * Created by yzy on 2019-11-01 17:40
 */
public class SearchInBinaryArray {

    public static void main(String[] args) {

    }


    /**
     * 解题思路：
     * 由于从左到右，从上到下，都是有序的
     * 所以可以从左下角，或者右上角开始找。
     *
     * 以左下角为例，小于target则往右找，大于target则往上找，直到找到或者到达数组边界
     * @param target
     * @param array
     * @return
     */
    public static boolean Find(int target, int [][] array) {
        int h = array.length-1;
        int w = 0;
        while(h>=0 && w<array[0].length){
            int tmp = array[h][w];
            if(tmp > target){
                h--;
            } else if(tmp < target){
                w++;
            } else {
                return true;
            }
        }
        return false;
    }
}
